package pri.zjy.dynamicProgramming;

/**
 * @author zhangjy
 * @description 使用最小花费爬楼梯
 * @date 2025/5/26 17:06
 */
public class MinCostClimbingStairs_746 {

    public static void main(String[] args) {
        MinCostClimbingStairs_746 minCostClimbingStairs746 = new MinCostClimbingStairs_746();

        int[] cost = {10, 15, 20};
//        int[] cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
        System.out.println(minCostClimbingStairs746.minCostClimbingStairs(cost));
        System.out.println(minCostClimbingStairs746.minCostClimbingStairs2(cost));
    }

    /**
     * 个人解法：dp-状态压缩
     * <p>
     * 分析：
     * 根据普通dp改造，优化空间复杂度。
     */
    public int minCostClimbingStairs2(int[] cost) {
        if (cost.length < 2) return 0;

        // 1.dp[i]表示，爬到第 i 个台阶上，所需的最低花费。
        // 要求爬上第 cost.length 个台阶；cost[i]表示，从第 i 个台阶向上爬 1或2 个台阶，所需要的花费。
//        int[] dp = new int[cost.length + 1];

        // 2.递推公式
        // 每次爬 1或2 个台阶；要爬到第 i 个台阶，就要分别看前两个台阶的最低花费，以及从这两个台阶向上爬的花费。
//        dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);

        // 3.初始化
        // dp[i]表示爬到第i个台阶上，所需的最低花费，但是站在0、1号台阶上，并不需要花费；所以它俩初始化都为0。
        int n1 = 0, n2 = 0, n3 = 0;

        // 4.遍历顺序
        // 由于dp[i]依赖于前两项，所以从前往后遍历；
        for (int i = 2; i < cost.length + 1; i++) {
//            dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
            // 获取dp[i]
            n3 = Math.min(n2 + cost[i - 2], n1 + cost[i - 1]);

            // 分别更新n1、n2为下一个循环中最新的前两项，即dp[i-1]、dp[i-2]
            n2 = n1;
            n1 = n3;

            // 5.打印日志
            if (n2 + cost[i - 2] <= n1 + cost[i - 1]) {
                // 从i-2开始爬花费更小
                System.out.println("dp[" + i + "]=" + n3 + " = " + "dp[" + (i - 2) + "]=" + n2 + " + " + "cost[" + (i - 2) + "]=" + cost[i - 2]);
            } else {
                System.out.println("dp[" + i + "]=" + n3 + " = " + "dp[" + (i - 1) + "]=" + n1 + " + " + "cost[" + (i - 1) + "]=" + cost[i - 1]);
            }
        }

        // 爬到第cost.length个台阶上（也就是爬到楼顶），所需的最低花费
        return n3;
    }

    /**
     * 个人解法：dp
     */
    public int minCostClimbingStairs(int[] cost) {
        if (cost.length < 2) return 0;

        // 1.dp[i]表示，爬到第 i 个台阶上，所需的最低花费。
        // 要求爬上第 cost.length 个台阶；cost[i]表示，从第 i 个台阶向上爬 1或2 个台阶，所需要的花费。
        int[] dp = new int[cost.length + 1];

        // 2.递推公式
        // 每次爬 1或2 个台阶；要爬到第 i 个台阶，就要分别看前两个台阶的最低花费，以及从这两个台阶向上爬的花费。
//        dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);

        // 3.初始化
        // dp[i]表示爬到第i个台阶上，所需的最低花费，但是站在0、1号台阶上，并不需要花费；所以它俩初始化都为0。
        // 为什么不是dp[0]=cost[0]、dp[1]=cost[1]？——因为由题目“你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 可知，到达 第 0或1 个台阶是不花费的，但从 第 0或1 个台阶 往上爬的话，需要花费 cost[0]、cost[1]。
        dp[0] = 0;
        dp[1] = 0;

        // 4.遍历顺序
        // 由于dp[i]依赖于前两项，所以从前往后遍历；
        // 为什么i < cost.length + 1？——是因为题目是爬到楼顶，那么第 cost.length 号台阶也需要爬才能到楼顶。
        for (int i = 2; i < cost.length + 1; i++) {
            dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);

            // 5.打印日志
            if (dp[i - 2] + cost[i - 2] <= dp[i - 1] + cost[i - 1]) {
                // 从i-2开始爬花费更小
                System.out.println("dp[" + i + "]=" + dp[i] + " = " + "dp[" + (i - 2) + "]=" + dp[i - 2] + " + " + "cost[" + (i - 2) + "]=" + cost[i - 2]);
            } else {
                System.out.println("dp[" + i + "]=" + dp[i] + " = " + "dp[" + (i - 1) + "]=" + dp[i - 1] + " + " + "cost[" + (i - 1) + "]=" + cost[i - 1]);
            }
        }

        // 爬到第cost.length个台阶上（也就是爬到楼顶），所需的最低花费
        return dp[cost.length];
    }

}
